競プロ典型 90 問 012
(工事中)
解き方
解答例
下は上記の方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。
code: C
typedef struct btree {
int pri;
struct btree *left;
struct btree *right;
struct btree *parent;
} btree;
void print_btree(btree *t) {
if (t == NULL) {
return;
}
print_btree(t->left);
printf("(%d, %d, %d) ", t->pri, t->p0, t->p1); print_btree(t->right);
if (t->parent == NULL) {
printf("\n");
}
return;
}
btree *merge_btree(btree *t1, btree *t2, btree *parent) {
if (t1 == t2) {
return t1;
}
if (t1 == NULL) {
t2->parent = parent;
return t2;
}
if (t2 == NULL) {
t1->parent = parent;
return t1;
}
if (t1->pri < t2->pri) {
return merge_btree(t2, t1, parent);
}
t1->parent = parent;
if (t1->left == NULL || (t1->right != NULL && t1->left->pri > t2->pri)) {
t1->left = merge_btree(t1->left, t2, t1);
} else {
t1->right = merge_btree(t1->right, t2, t1);
}
return t1;
}
btree *make_node(int r, int c, btree *pool, int *used) {
int pri = rand();
btree *node = pool + *used;
*used = *used + 1;
node->pri = pri;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
return node;
}
btree *get_root(btree * t) {
if (t == NULL) {
return t;
}
while(t->parent != NULL) {
t = t->parent;
}
return t;
}
int main () {
int h = 0;
int w = 0;
int q = 0;
int res = 0;
int used = 0;
srand((unsigned int)time(NULL));
res = scanf("%d", &h);
res = scanf("%d", &w);
res = scanf("%d", &q);
for (int i = 0; i < q; i++) {
int t = 0;
res = scanf("%d", &t);
if (t == 1) {
int r = 0;
int c = 0;
res = scanf("%d", &r);
res = scanf("%d", &c);
int d42 = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; btree *group = NULL;
map_trc = make_node(r, c, pool, &used); for (int i = 0; i < 4; i++) {
group = merge_btree(group, get_root(map_tnrnc), NULL); }
}
}
}
if (t == 2) {
int ra = 0;
int ca = 0;
int rb = 0;
int cb = 0;
btree *roota = NULL;
btree *rootb = NULL;
res = scanf("%d", &ra);
res = scanf("%d", &ca);
res = scanf("%d", &rb);
res = scanf("%d", &cb);
if (roota == NULL || rootb == NULL || get_root(roota) != get_root(rootb)) {
printf("No\n");
} else {
printf("Yes\n");
}
}
}
return 0;
}
私の提出一覧
table: submissions_atcoder_typical90_012
提出のURL 提出時刻 結果 備考
感想
ローカルにおいてあったzakkan.txt（雑感）には、まだ書かれていないので、こっちに直接書く
この問題は印象深いため覚えている。
確か、悩んだ末に各ノードの親を毎回根に付け替えるようなことをする木で管理するようにして解いたが、
後から調べてみたら、Union Find の考え方とほぼ同等だった（？）という記憶。つまり、所謂ところの再開発
再開発→再発明（？）
最初、赤に塗られたマスを二分探索木で管理したら解けるのではないかと思って考えていた。
（当時は効率よく計算するためのデータ構造として二分探索木くらいしか知らなかったので、とりあえず木を考えていたフシがある）
しかし、それだとうまくいかないことに気づき、改めて悩む。その末に、木を考えていたこともあってか、親を根に付け替えることを思いつく。
そんな経緯があったので、上のソースコードでは、二分探索木として考えていた形跡が残っていたかな笑
union find が必要なときに私が今
union find として私が書くときの形はほぼ決まっているが、この時点では二分探索木の面影が残っているので、今の形になったのはいつだろう？
union find 自体は名前を見かけたことはあったが、慣れるまでは競技プログラミングによく使うテクニックを調べるのは控えようと考えていたため、内容をあえて見ないようにしていた。
後日に内容をみてみると、ああこのとき考えていたものと同じね、となったかな。
そんなこともあり、もうそろそろその段階かなと思い、競技プログラミングとしてのテクニックについても
それまではコンテスト中に解けない問題にあたったときに検索するぐらいだったかな。
と思ったが、上の経緯を考えると、きっかけはそこではなかった気がしてきた。これがきっかけと記憶していたが、どうだったかな。
とりあえず、なにかのきっかけで、そういうテクニックを調べるのを解禁して、そこで…上の感じ
ありそうなのは、コンテストでunion find を使う問題が出たか？それで上の流れに
他の問題でも再開発があって、2次元imos というらしい方法は、それもかなり悩んだ覚えがあるが自力かな。
imos や累積和を使うのは、コンテストで出た問題の解説をみて、覚えた気もする。どうだったかな